package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:最大子数组和
 *
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组 是数组中的一个连续部分。
 *
 *
 *
 * 示例 1：
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组[4,-1,2,1] 的和最大，为6 。
 *
 * 示例 2：
 * 输入：nums = [1]
 * 输出：1
 *
 * author: Mr.Du
 * Date: 2022/11/9
 * Time: 19:59
 */
public class MaxSubArray {
    
    /**
     * 用两个变量解决
     *      res:用来记录结果
     *      sum:用来进行和操作
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0)
                sum += num;
            else
                sum = num;
            res = Math.max(res, sum);
        }
        return res;
    }
    
    /**
     *  dp[i]表示[0,i]之间最大的连续子数组之和
     *      有两种操作：
     *          第一种：自己组成一个子数组nums[i]
     *          第二种：自己和dp[i-1]组成一个子数组
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums){
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        for(int i = 1;i < len;i++){
            dp[i] = Math.max(dp[i-1] + nums[i],nums[i]);
        }
        int max = Integer.MIN_VALUE;
        for(int i : dp){
            max = Math.max(i,max);
        }
        return max;
    }
}
